package com.peng.leetcode.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * LongestUnivaluePath
 *
 * @author lupeng <lupeng@kuaishou.com>
 * Created on 2021-05-16
 */
public class LongestUnivaluePath {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 3, 2, 4, 4, 2};
        int[] ints = new LongestUnivaluePath().removeRepeat(arr);
        System.out.println(ints);
    }

    private int answer = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return answer;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        int left = dfsCal(node.left, node.val, 0);
        int right = dfsCal(node.right, node.val, 0);
        answer = Math.max(answer, left + right);
        dfs(node.left);
        dfs(node.right);
    }

    private int dfsCal(TreeNode node, int value, int path) {
        if (node == null) {
            return path;
        }
        if (node.val != value) {
            return path;
        } else {
            path += 1;
            return Math.max(dfsCal(node.left, value, path), dfsCal(node.right, value, path));
        }
    }


    private int[] removeRepeat(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        stack.offer(nums[0]);
        int index = 1;
        while (index < nums.length) {
            int removeNum;
            int n = nums[index];
            if (stack.peekLast() == n) {
                stack.pollLast();
                removeNum = n;
                while (nums[index] == removeNum) {
                    index++;
                }
            } else {
                stack.offer(n);
            }
            index++;
        }
        return stack.stream().mapToInt(i -> i).toArray();
    }
}
